#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int maxSumAfterPartitioning(vector<int> &arr, int k)
    {
        if (arr.size() == 1)
            return arr[0];
        vector<int> dp(arr.size() + 1);
        dp[0] = 0;
        for (int i = 0; i < arr.size(); i++)
        {
            int max_val = arr[i];
            for (int j = 1; j <= min(k, i + 1); j++)
            {
                max_val = max(max_val, arr[i - j + 1]);
                dp[i + 1] = max(dp[i + 1], dp[i - j + 1] + max_val * j);
            }
        }
        return dp[arr.size()];
    }
};
int main()
{
    cout << "Code1043" << endl;
    Solution s;
    vector<int> arr = {1, 15, 7, 9, 2, 5, 10};
    cout << s.maxSumAfterPartitioning(arr, 3) << endl;
    return 0;
}